package history.hot100;

// 221. 最大正方形
public class LeetCode_221 {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return maxSide;
        int rows = matrix.length, columns = matrix[0].length;
        int [][]state = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i==0||j==0) {
                        state[i][j] = 1;
                    } else {
                        state[i][j] = Math.min(Math.min(state[i-1][j], state[i][j-1]), state[i-1][j-1])+1;
                    }
                    maxSide = Math.max(maxSide, state[i][j]);
                }
            }
        }
        int maxSquare = maxSide*maxSide;
        return maxSquare;
    }
}
